/**
 * @author LKQ
 * @date 2022/1/7 18:24
 * @description
 */
public class Solution {
    public static void main(String[] args) {
        TreeNode t3 = new TreeNode(3), t5 = new TreeNode(5), t4 = new TreeNode(4, t3, t5),
                t0 = new TreeNode(0), t2 = new TreeNode(2, t0, t4), t7 = new TreeNode(7),
                t9 = new TreeNode(9), t8 = new TreeNode(8, t7, t9), t6 = new TreeNode(6, t2, t8);
        Solution solution = new Solution();
        solution.lowestCommonAncestor(t6, t2, t4);
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode temp = root;
        while (temp != null) {
            if (p.val < temp.val && q.val < temp.val) {
                // 两边都在左
                temp = temp.left;
            }else if (p.val > temp.val && q.val > temp.val) {
                temp = temp.right;
            }else {
                break;
            }
        }
        return temp;
    }
}
